#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <memory.h>
#include <stdio.h>
#include <math.h>

#define Start 4000  //可提高以提高通过率
#define End 1e-7
#define Reduce 0.5  //可提高以提高通过率
#define Max 100000
#define Loop 3      //可提高以提高通过率
int map[Max];
int max;
int len;

int serch(int list[]) {
    int Newmap[Max], newmax = max;
    memcpy(Newmap, map, sizeof(int) * Max);
    int i, j;
    for (i = 0; i < len; i++) {
        while (Newmap[newmax] == 0)newmax--;
        if (newmax < list[i])return i;
        Newmap[newmax]--;
        Newmap[newmax - list[i]]++;
    }
    return -1;
}

void swap(int *a, int *b) {
    int m = *a;
    *a = *b;
    *b = m;
}

bool canDistribute(int *nums, int numsSize, int *quantity, int quantitySize) {
    int value[1001];
    memset(value, 0, sizeof(value));
    memset(map, 0, sizeof(map));
    len = 0;
    int i, j, k;
    max = 0;
    for (i = 0; i < numsSize; i++) {
        value[nums[i]]++;
    }
    for (i = 0; i <= 1000; i++) {
        map[value[i]]++;
        if (value[i] > max)max = value[i];
    }
    for (i = 0; i < quantitySize; i++)if (quantity[i] > max)return 0; //如果最大的背包都装不下了 直接返回0
    for (i = 0; i < quantitySize; i++) { //优化，如果有背包能刚好装下一个订单就直接装进去把订单删掉
        k = quantity[i];
        if (map[k]) {
            map[k]--;
            quantity[i] = 0;
            continue;
        }
        for (j = i + 1; j < quantitySize; j++) {
            if (quantity[j] == 0)continue;
            int y = quantity[j];
            if (map[k + y]) {
                map[k + y]--;
                quantity[i] = 0;
                quantity[j] = 0;
            }
        }
    }
    int list[quantitySize];
    for (i = 0; i < quantitySize; i++) {
        if (quantity[i] != 0)list[len++] = quantity[i];
    }
    if (len == 0) {
        return true;
    }
    int V = serch(list);
    if (V == -1)return 1;
    if (len == 1)return 0;


    double Tem = Start, r;
    srand((unsigned) time(0));
    int left, right;  //开始退火咯
    while (Tem > End) {

        for (j = 0; j < Loop; j++) {

            do {
                left = rand() % len;
                right = rand() % len;
            } while (left == right);


            swap(&list[left], &list[right]);
            int newV = serch(list);
            if (newV == -1)return 1;
            if (newV > V) { V = newV; }
            else {
                r = rand();
                r /= (RAND_MAX);
                double va = exp(-(V - newV) / Tem);
                if (va < r) {
                    swap(&list[left], &list[right]);
                }
            }
            if (serch(list) == 0)return 1;
        }
        Tem *= Reduce;
    }
    return 0;
}

int main()
{
    int nums[4] = {1,2,3,3}, quantity[1] = {2};
    int ret = canDistribute(nums, 4, quantity, 1);
    printf("%d", ret);
}

